#include <functional>
#include <algorithm>
#include "cmf.h"
#include "goloso.h"

CliqueMaximaFronteraGoloso::CliqueMaximaFronteraGoloso(const Grafo& g) : CliqueMaximaFrontera(g) {
	
}

set<uint> CliqueMaximaFronteraGoloso::resolver() {		
	set<uint> solucion;
	set<uint> nodos = grafo.conjuntoNodos();
	uint fronteraActual = 0;
	uint fronteraMaxima = 0;
	uint gradosActuales = 0;
	
	while (true) {
		if (nodos.empty())
			break;
		uint nodoMaxGrado = maximo(nodos);
		gradosActuales += grafo.miGrado(nodoMaxGrado);
		fronteraActual = gradosActuales - solucion.size() * (solucion.size()+1);
		
		if (fronteraMaxima < fronteraActual) {
			solucion.insert(nodoMaxGrado);
			nodos = grafo.adyacentes(nodoMaxGrado, nodos);
			fronteraMaxima = fronteraActual;
		} else {
			break;
		}
	}

	return solucion;
}

uint CliqueMaximaFronteraGoloso::maximo(const set<uint> &nodos) {
	uint max = 0;
	uint res = 0;
	
	for(set<uint>::iterator it = nodos.begin(); it != nodos.end(); it++) {
		if (grafo.miGrado(*it) > max) {
			res = *it;
			max = grafo.miGrado(*it);
		}
	}
	return res;
}

